//
// Created by DengLibin on 2018/12/16 0016.
//
/**
 * 二叉排序树
 */

#include <iostream>
using namespace std;
//节点
class Node
{
public:
    int num;//节点的值
    Node * leftNode = nullptr;//左子节点
    Node * rightNode = nullptr;//右子节点
    Node * parentNode = nullptr;//父节点
};
//排序树
class SortTree
{
private:
    Node * rootNode;//树的根节点
    int size;//节点个数

    //先序遍历
    void preShow(Node * node, int deep)
    {
        if (node == nullptr)
        {
            return;
        }
        for (int i = 0; i < deep; i++)
        {
            cout << "-";
        }
        cout << node->num << endl;
        deep++;
        preShow(node->leftNode,deep);
        preShow(node->rightNode,deep);
    }
    //中序遍历
    void inShow(Node *node)
    {
        if (node == nullptr)
        {
            return;
        }
        inShow(node->leftNode);
        cout << node->num << endl;
        inShow(node->rightNode);
    }

    void release(Node * rootNode)
    {
        if (rootNode == nullptr)
        {
            return;
        }
        release(rootNode->leftNode);
        release(rootNode->rightNode);
        delete rootNode;
    }
public:
    SortTree() //构造函数
    {
    }

    ~SortTree()
    {
        //析构
        release(this->rootNode);
    }

    /*获取根节点*/
    Node* getRoot() { return this->rootNode; }
    /*将键值key插入到二叉树中*/
    void insert(int key)
    {
        //创建一个节点
        Node * insertNode = new Node();
        insertNode->num = key;
        if (this->size == 0)
        {
            this->rootNode = insertNode;
            size++;
            return;
        }
        //寻找插入位置
        Node * tempNode = rootNode;
        while (tempNode != nullptr)
        {
            if (insertNode->num > tempNode->num)
            {
                if (tempNode->rightNode == nullptr)
                {
                    tempNode->rightNode = insertNode;
                    insertNode->parentNode = tempNode;
                    break;
                }
                else
                {
                    tempNode = tempNode->rightNode;
                    continue;
                }
            }
            else
            {
                if (tempNode->leftNode == nullptr)
                {
                    tempNode->leftNode = insertNode;
                    insertNode->parentNode = tempNode;
                    break;
                }
                else
                {
                    tempNode = tempNode->leftNode;
                    continue;
                }
            }
        }
    }
    //先序遍历
    void preShow()
    {
        preShow(this->rootNode,0);
    }

    //中序遍历 (从小到大遍历)
    void inShow()
    {
        inShow(this->rootNode);
    }

    //查找
    int search(int key)
    {
        Node * tempNode = rootNode;
        while (tempNode != nullptr)
        {
            if (key == tempNode->num)
            {
                return tempNode->num;
            }
            else
            {
                if (key > tempNode->num)
                {
                    tempNode = tempNode->rightNode;
                }
                else
                {
                    tempNode = tempNode->leftNode;
                }
            }
        }
        return -1;
    }

};

int main41(void)
{
    SortTree * tree = new SortTree();
    int arr[9] = {8,3,10,1,6,14,4,7,13};
    for (int i = 0; i < 9; i++)
    {
        tree->insert(arr[i]);
    }
    //tree->preShow();
    //tree->inShow();
    cout << tree->search(2);
    delete tree;
    return 0;
}